/************************************
 * created by Tonk (tonk@ctonk.com) *
 ************************************/

// LinkedList.cpp

/*
 * LinkedList is a template class for a dynamic array. I wrote
 * it because I used to dislike the STL syntax, and wanted a
 * dynamic array completely free of STL dependencies.
 * (In contrast to my Magiclist, which is simply a container
 *  for the std::list object)
 *
 * The LinkedList class uses three other classes to function,
 * the Node class, which is a container for the element data,
 * and the HeadNode and TailNode classes, which derive from
 * Node and simply exist to bind the list.
 *
 * LinkedList, by default, has one each HeadNode and TailNode
 * objects to create the foundation of the list. For each
 * element that is added to the list, a Node object is created
 * as the container for that element.
 *
 * The Node setup is the backbone of the list. Each Node has
 * two Node pointers, one called _next and one called _last.
 *
 * Long story short, this is how the list works, and what
 * happens when you add a new list element:
 * 1) A Node object is created as a container for the element.
 * 2) The Node is inserted, using pointer arithmetic, just in
 *    front of the TailNode. To do that, the following steps
 *    are taken:
 *     a) TailNode._last is set to point to the newly added Node.
 *     b) What used to be the last list element's _next pointer is
 *        set to point to the new Node.
 *     c) The newly added Node's _next pointer is set to TailNode.
 *     d) The newly added Node's _last pointer is set to what used
 *        to be the last Node.
 * 3) That being done, the new element has successfully been added
 *    to the end of the list, and LikedList._size is incremented.
 * 4) When removing an element, the reverse process is used.
 * 5) Simple enough, right? :D
 *
 */

#ifndef CPP_LLIST
#define CPP_LLIST



//////////////////// Node ////////////////////

template <class T> class Node {
	// Data container for the LinkedList.
	protected:
		Node< T >* _next;
		Node< T >* _last;
		T* _data;
	public:
		Node( void );
		Node( Node< T >& );
		virtual ~Node();

		Node< T >& operator= ( Node< T >& );

		Node< T >* GetNext();
		void SetNext( Node< T >* );
		Node< T >* GetLast();
		void SetLast( Node< T >* );
		T& GetData();
		void SetData( T& );
};

template <class T> Node< T >::Node( void ) {
	// Default constructor
	this->_next = 0;
	this->_last = 0;
	this->_data = new T;
}

template <class T> Node< T >::Node( Node< T >& node ) {
	// Copy constructor
	this->_next = node.GetNext();
	this->_last = node.GetLast();
	this->_data = node.GetData();
}

template <class T> Node< T >::~Node() {
	// Destructor
	delete _data;
}

template <class T> Node< T >& Node< T >::operator= ( Node< T >& node ) {
	// Overloaded '=' operator
	this->_next = node.GetNext();
	this->_last = node.GetLast();
	this->_data = node.GetData();
}

template <class T> Node< T >* Node< T >::GetNext() {
	// Returns next Node in list.
	return this->_next;
}

template <class T> void Node< T >::SetNext( Node< T >* next ) {
	// Sets the next Node.
	this->_next = next;
}

template <class T> Node< T >* Node< T >::GetLast() {
	// Returns the last Node.
	return this->_last;
}

template <class T> void Node< T >::SetLast( Node< T >* last ) {
	// Sets the last Node.
	this->_last = last;
}

template <class T> T& Node< T >::GetData() {
	// Return the element object from this Node.
	return *(this->_data);
}

template <class T> void Node< T >::SetData( T& t ) {
	// Set the element object of this Node.
	*(this->_data) = t;
}

//////////////////// End Node ////////////////////





//////////////////// HeadNode ////////////////////

template <class T> class HeadNode : public Node< T > {
	// Holds no actual data; just marks the beginning of the LinkedList.
	protected:
	public:
		HeadNode();
		~HeadNode();
};

template <class T> HeadNode< T >::HeadNode() {
	// Default constructor
}

template <class T> HeadNode< T >::~HeadNode() {
	// Destructor
}

//////////////////// End HeadNode ////////////////////





//////////////////// TailNode ////////////////////

template <class T> class TailNode : public Node< T > {
	// Holds no actual data; just marks the end of the LinkedList.
	protected:
	public:
		TailNode();
		~TailNode();
};

template <class T> TailNode< T >::TailNode() {
	// Default constructor
}

template <class T> TailNode< T >::~TailNode() {
	// Destructor
}

//////////////////// End TailNode ////////////////////





//////////////////// LinkedList ////////////////////

template <class T> class LinkedList {
	// Dynamic allocation container class.
	protected:
		HeadNode< T >* _head;
		TailNode< T >* _tail;
		int _size;
	public:
		LinkedList( void );
		LinkedList( int );
		LinkedList( LinkedList< T >& );
		~LinkedList();

		T& operator[] ( int );
		LinkedList< T >& operator= ( LinkedList< T >& );
		LinkedList< T >& operator+= ( LinkedList< T >& );
		
		int GetSize();
		T& GetFirst();
		T& GetLast();
		T& Add( void );
		T& Add( T& t );
		void Remove( T& );
		void Resize( int );
		void Purge();
};

template <class T> LinkedList< T >::LinkedList( void ) {
	// Default constructor
	this->_head = new HeadNode< T >;
	this->_tail = new TailNode< T >;
	this->_head->SetNext( this->_tail );
	this->_tail->SetLast( this->_head );
	this->_size = 0;
}

template <class T> LinkedList< T >::LinkedList( int size ) {
	// Constructor with defined starting size
	this->_head = new HeadNode< T >;
	this->_tail = new TailNode< T >;
	this->_head->SetNext( this->_tail );
	this->_tail->SetLast( this->_head );
	this->_size = 0;
	Resize( size );
}

template <class T> LinkedList< T >::~LinkedList() {
	// Destructor
	this->Purge();
	delete this->_head;
	delete this->_tail;
}

template <class T> T& LinkedList< T >::operator[] ( int n ) {
	// Returns the nth element of the list.
	// If n is too high/low, the last/first list element will be returned instead.
	if ( _size == 0 )
		this->Add();
	if ( n < 0 )
		return this->GetFirst();
	if ( n > _size )
		return this->GetLast();

	Node< T >* node = this->_head->GetNext();
	for ( int x=0; x < n; x++ )
		node = node->GetNext();
	return node->GetData();
}

template <class T> LinkedList< T >& LinkedList< T >::operator= ( LinkedList< T >& list ) {
	// Overwrites the contents of the list with those of the given list.
	this->Resize( list.GetSize() );
	int x=0;
	for ( Node< T >* node = this->_head->GetNext(); node != this->_tail; node = node->GetNext() ) {
		node->SetData( list[x] );
		x++;
	}
	return *this;
}

template <class T> LinkedList< T >& LinkedList< T >::operator+= ( LinkedList< T >& list ) {
	// Appends the elements of the given list.
	for ( int x=0; x < list.GetSize(); x++ )
		this->Add( list[x] );
	return *this;
}

template <class T> int LinkedList< T >::GetSize() {
	// Returns the list size.
	return this->_size;
}

template <class T> T& LinkedList< T >::GetFirst() {
	// Returns the first list element.
	return ( this->operator[] ( 0 ) );
}

template <class T> T& LinkedList< T >::GetLast() {
	// Returns the last list element.
	return ( this->operator[] ( this->GetSize() - 1 ) );
}

template <class T> T& LinkedList< T >::Add( void ) {
	// Adds a new list element, does not initialize data.
	Node< T >* node = new Node< T >;
	this->_tail->GetLast()->SetNext( node );
	node->SetLast( this->_tail->GetLast() );
	this->_tail->SetLast( node );
	node->SetNext( this->_tail );
	this->_size++;
	return node->GetData();
}

template <class T> T& LinkedList< T >::Add( T& t ) {
	// Adds a new list element, then sets the object to 't'.
	this->Add() = t;
	return t;
}

template <class T> void LinkedList< T >::Remove( T& t ) {
	// Removes the first list element with data matching 't'.
	for ( Node< T >* node = this->_head->GetNext(); node != this->_tail; node = node->GetNext() )
	{
		if ( &( node->GetData() ) == &t )
		{
			node->GetLast()->SetNext( node->GetNext() );
			node->GetNext()->SetLast( node->GetLast() );
			delete node;
			_size--;
			return;
		}
	}
	return;
}

template <class T> void LinkedList< T >::Resize( int size ) {
	// Resizes the list.
	// Does nothing when size is either negative or same as current size.
	// The list will not be deleted and recreated. In other words:
	// If size is larger than this->GetSize(), new elements will be added.
	// If size is smaller than this->GetSize(), list will simply be truncated.
	if ( size < 0 || size == this->_size )
		return;
	else if ( this->_size > size )
	{
		int difference = this->_size - size;
		Node< T >* node = 0;
		for ( int x=0; x < difference; x++ )
		{
			node = this->_tail->GetLast();
			node->GetLast()->SetNext( this->_tail );
			this->_tail->SetLast( node->GetLast() );
			delete node;
		}
	}
	else
	{
		int difference = size - this->_size;
		for ( int x=0; x < difference; x++ )
			this->Add();
	}

	this->_size = size;
	return;
}

template <class T> void LinkedList< T >::Purge() {
	// Removes all list elements and sets size to 0.
	Resize( 0 );
	return;
}

//////////////////// End LinkedList ////////////////////





/*int main() { // This is just here for ease of testing/debugging.
	return 0;
}*/


#endif // #ifndef CPP_LLIST